package basic.study.wantOffer.chapter6;

/**
 * @ClassName Problem68
 * @Description 树中两个结点的最低公共祖先
 * @Company inspur
 * @Author Kevin
 * @Date 2020/6/15 12:46
 * @Version 1.0
 */
public class Problem68 {
    /**
     * 哈哈，LCA问题，来默写
     * 情况1：普通二叉树
     */
    public Node getLowestCommonParentBST(Node root, Node p, Node q) {
        if (root == null) {
            return root;
        }
        if (root == p || root == q) {
            return root;
        }
        Node left = getLowestCommonParentBST(root.left, p, q);
        Node right = getLowestCommonParentBST(root.right, p, q);
        if (left != null && right != null) {
            return root;
        } else if (left == null) {
            return right;
        } else {
            return left;
        }
    }

    /**
     * 二叉搜索树
     * 利用大小关系即可
     */
    public Node getLowestCommonParentBST2(Node root, Node p, Node q) {
        while (true) {
            if (root == null) {
                return root;
            }
            if (root.val < p.val && root.val < q.val) {
                root = root.right;
            } else if (root.val > p.val && root.val > q.val) {
                root = root.left;
            } else {
                return root;
            }
        }
    }

    class Node {
        Node left;
        Node right;
        int val;
    }
}
